11593. Преобразовать в перестановку

Имеется массив A размера n. За одну операцию можно выбрать индекс i (1 ≤ i ≤ n) и увеличить A_i на 1.

Найдите минимальное количество операций, необходимое для преобразования массива A в перестановку размера n. Если это невозможно, выведите -1.

Обратите внимание, что перестановка размера n содержит каждый элемент от 1 до n ровно один раз.

Вход. Первая строка содержит количество тестов T.

Каждый тест состоит из нескольких строк. Первая строка каждого теста содержит одно целое число n (1 ≤ n ≤ 1000) – размер массива. В следующей строке записаны n целых чисел – элементы массива A (0 ≤ A_i ≤ 1000).

Выход. Для каждого теста выведите в новой строке минимальное количество операций, необходимое для преобразования массива A в перестановку размера n.

Если это сделать невозможно, то выведите -1.

Пример входа	Пример выхода
4 4 3 1 1 2 3 0 3 3 3 3 2 1 3 2 0 1	3 -1 0 3

РЕШЕНИЕ

жадность

Анализ алгоритма

Отсортируем входной массив: a₀, a₁, …, a_{n – 1}. Для того чтобы получить перестановку (1, 2, …, n), необходимо произвести следующие преобразования:

a₀ → 1, a₁ → 2, …, a_{n – 1} → n

То есть из числа a_i следует сделать i + 1. Нам доступна только одна операция по преобразованию чисел: увеличение на 1. Если изначально a_i > i + 1, то из a_i получить i + 1 невозможно. Иначе i + 1 из a_i можно получить за i + 1 – a_i операций. Осталось просуммировать это количество операций для каждого i от 0 до n – 1.

Пример

Отсортируем массив в первом тесте: (1, 1, 2, 3). Нам следует получить перестановку (1, 2, 3, 4). Количество операций равно

(1 – 1) + (2 – 1) + (3 – 2) + (4 – 3) = 0 + 1 + 1 + 1= 3

Во втором тесте после сортировки массив примет вид: (0, 3, 3). Получить перестановку (1, 2, 3) невозможно, так как нельзя a₁ = 3 преобразовать в 2.

Реализация алгоритма

Читаем количество тестов tests.

scanf("%d", &tests);

while (tests--)

{

Читаем входные данные текущего теста.

scanf("%d", &n);

v.clear(); v.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &v[i]);

Сортируем массив.

sort(v.begin(), v.end());

В переменной res подсчитываем минимальное количество операций по преобразованию входной последовательности в перестановку размера n.

res = 0;

Перебираем индексы i от 0 до n – 1.

for (i = 0; i < n; i++)

{

Если v_i > i + 1, то из v_i получить i + 1 невозможно. Преобразовать входной массив в перестановку нельзя.

if (v[i] > i + 1)

{

res = -1;

break;

}

Суммируем требуемое количество операций.

res += (i + 1 - v[i]);

}

Выводим ответ.

printf("%d\n", res);

}